/*
 * Copyright [2010] [Daniel H. Cavalcanti]
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.collections;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * A default heap implementation.
 *
 * @author Daniel Cavalcanti
 */
public abstract class AbstractHeap<E>
    implements Heap<E> {

    // *************************************************************************
    // Instance variables
    // *************************************************************************

    final ReadWriteLock lock = new ReentrantReadWriteLock(true);

    final Comparator<? super E> comparator;

    transient int size;
    transient E[] heap; // index 0 is never used.

    // *************************************************************************
    // Constructors
    // *************************************************************************

    public AbstractHeap() {
        this((Comparator) null);
    }

    public AbstractHeap(Comparator<? super E> comparator) {
        this.comparator = comparator;
        heap = (E[]) new Object[17];
    }

    public AbstractHeap(Collection<E> collection) {
        this(collection, null);
    }

    public AbstractHeap(Collection<E> collection, Comparator<? super E> comparator) {
        this(comparator);

        size = collection.size();
        heap = (E[]) new Object[collection.size()+1];
        
        Iterator<E> iterator = collection.iterator();
        for (int i = 1 ; i <= size ; i++)
            heap[i] = iterator.next();

        for (int i = size/2 ; i > 0 ; i--)
            bubbleDown(i);

    }

    // *************************************************************************
    // Heap methods
    // *************************************************************************

    public int size() {
        lock.readLock().lock();
        try {
            return size;
        } finally {
            lock.readLock().unlock();
        }
    }

    public boolean isEmpty() {
        lock.readLock().lock();
        try {
            return size == 0;
        } finally {
            lock.readLock().unlock();
        }
    }

    public E peek() {
        lock.readLock().lock();
        try {
            return isEmpty() ? null : heap[1];
        } finally {
            lock.readLock().unlock();
        }
    }

    public void insert(E e)
    throws NullPointerException {
        if (e == null)
            throw new NullPointerException();

        lock.writeLock().lock();
        try {

            size++;
            resize();

            heap[size] = e;
            bubbleUp(size);

        } finally {
            lock.writeLock().unlock();
        }
    }

    public E remove() {
        lock.writeLock().lock();
        try {

            if (isEmpty())
                return null;

            E root = heap[1];
            swap(1,size);

            size--;
            resize();

            bubbleDown(1);
            return root;

        } finally {
            lock.writeLock().unlock();
        }
    }

    // *************************************************************************
    // Auxiliary methods
    // *************************************************************************

    /**
     * Returns the index of the element that should be the parent when comparing
     * the two elements at position <code>i</code> and <code>j</code>.
     * 
     * @param i The index of the first element.
     * @param j The index of the second element.
     * @return The index of the element that should be the parent.
     * @throws IndexOutOfBoundsException If both i and j are not withing the heap bounds.
     */
    protected abstract int getParentIndex(int i, int j)
    throws IndexOutOfBoundsException;

    protected void resize() {

        if (size >= heap.length*3/4) {
            E[] copy = (E[]) new Object[heap.length*2];
            System.arraycopy(heap, 0, copy, 0, Math.min(heap.length, copy.length));
            heap = copy;
        } else if (size <= heap.length/3+1) {
            E[] copy = (E[]) new Object[heap.length/2+1];
            System.arraycopy(heap, 0, copy, 0, Math.min(heap.length, copy.length));
            heap = copy;
        }

    }

    protected void swap(int i, int j) {
        E swap = heap[i];
        heap[i]=  heap[j];
        heap[j] = swap;
    }

    protected void bubbleUp(int index) {

        int p = index/2;
        int c = index;

        while (c > 1) {
            if (getParentIndex(c, p) == c) {
                swap(c, p);
                c = p;
                p /= 2;
            } else break;
        }

    }

    protected void bubbleDown(int index) {

        int p = index;
        int l = index*2;
        int r = index*2+1;

        while (p <= size/2) {
            int c = getParentIndex(l, r); // the winner child
            if (getParentIndex(c, p) == c) {
                swap(c, p);

                p = c;
                l = p*2;
                r = p*2+1;

            } else break;
        }

    }

}
